package 力扣.动态规划;

import 力扣.数组.哈希法.遍历Map的几种方式;

import java.util.Arrays;

public class 零钱兑换322 {
    public int coinChange(int[] coins, int amount)
    {
        // 没有解的时候，设置一个较大的值
        final int INF = Integer.MAX_VALUE / 4;

        int[] dp = new int[amount + 1];
        // 一开始给所有的数设置为不可解。
        for (int i = 1; i <= amount; i++) {
            dp[i] = INF;
        }

        // DP的初始条件
        dp[0] = 0;

        for (int i = 0; i < amount; i++) {
            for (int y : coins) {
                // 注意边界的处理，不要越界
                if (y <= amount && i + y < amount + 1 && i + y >= 0) {
                    // 正向推导时的递推公式!
                    dp[i + y] = Math.min(dp[i + y], dp[i] + 1);
                }
            }
        }

        return dp[amount] >= INF ? -1 : dp[amount];
    }
    public int coinChange2(int[] coins, int amount){
        //初始化dp数组
        int[] dp = new int[amount + 1];
        final int INF = Integer.MAX_VALUE / 4;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = INF;
        }
        dp[0] = 0;
        for (int i = 0; i < amount; i++) {
            for (int y : coins) {
                if (y <= amount && i + y < amount + 1 && i + y >= 0){//处理边界
                    dp[i + y] = Math.min(dp[i] + 1,dp[i + y]);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }

    public int coinChange3(int[] coins, int amount) {
       if (coins == null || amount == 0){
           return 0;
       }
       int[] dp = new int[amount + 1];
       int INF = Integer.MAX_VALUE / 4;
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 0; i < amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                int t = coins[j];
                if (t <= amount && (i + t) <= amount){
                    dp[i + t] = Math.min(dp[i + t],dp[i] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }

    public int coinChange4(int[] coins, int amount) {
         if (coins == null || coins.length == 0 || amount == 0){
             return 0;
         }
         int[] dp = new int[amount + 1];
         final int INF = Integer.MAX_VALUE / 4;
         Arrays.fill(dp,INF);
         dp[0] = 0;
        for (int i = 0; i < amount; i++) {
            for (int x:coins) {
                if (x < amount + 1  && i + x < amount + 1){
                    dp[i + x] = Math.min(dp[i + x],dp[i] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}
